// https://leetcode.cn/problems/sudoku-solver/description/

// 算法思路总结：
// 1. 回溯算法解决数独问题
// 2. 使用三个标记数组记录行、列、九宫格的数字使用情况
// 3. 预处理已填入数字，初始化标记数组
// 4. 递归尝试每个空格的1-9数字，满足数独规则
// 5. 找到解立即返回，避免不必要的搜索
// 6. 时间复杂度：O(9^(n))，空间复杂度：O(1)

#include <iostream>
using namespace std;

#include <vector>
#include <cstring>
#include <algorithm>

class Solution 
{
public:
    bool visRow[9][10] = {false};
    bool visCol[9][10] = {false};
    bool visGrip[3][3][10] = {false};

    void solveSudoku(vector<vector<char>>& board)
    {
        memset(visRow, 0, sizeof(visRow));
        memset(visCol, 0, sizeof(visCol));
        memset(visGrip, 0, sizeof(visGrip));

        for (int i = 0 ; i < 9 ; i++)
        {
            for (int j = 0 ; j < 9 ; j++)
            {
                if (board[i][j] != '.')
                {
                    int digit = board[i][j] - '0';
                    visRow[i][digit] = true;
                    visCol[j][digit] = true;
                    visGrip[i / 3][j / 3][digit] = true;
                }
            }
        }

        dfs(board, 0, 0);
    }

    bool dfs(vector<vector<char>>& board, int row, int col)
    {
        if (row == 9) return true;
        if (col == 9) return dfs(board, row + 1, 0);
        if (board[row][col] != '.') return dfs(board, row, col + 1);

        for (int i = 1 ; i <= 9 ; i++)
        {
            if (visRow[row][i] == false && visCol[col][i] == false && visGrip[row / 3][col / 3][i] == false)
            {
                board[row][col] = i + '0';
                visRow[row][i] = true;
                visCol[col][i] = true; 
                visGrip[row / 3][col / 3][i] = true;

                if (dfs(board, row, col + 1) == true)
                    return true;

                board[row][col] = '.';
                visRow[row][i] = false;
                visCol[col][i] = false; 
                visGrip[row / 3][col / 3][i] = false;
            }
        }
        return false;
    }

    void printBoard(const vector<vector<char>>& board) 
    {
        cout << "数独棋盘:" << endl;
        for (int i = 0; i < 9; i++) 
        {
            if (i % 3 == 0 && i != 0) 
            {
                cout << "------+-------+------" << endl;
            }
            for (int j = 0; j < 9; j++) 
            {
                if (j % 3 == 0 && j != 0) 
                {
                    cout << "| ";
                }
                cout << board[i][j] << " ";
            }
            cout << endl;
        }
    }
};

int main()
{
    vector<vector<char>> board = {
        {'5','3','.','.','7','.','.','.','.'},
        {'6','.','.','1','9','5','.','.','.'},
        {'.','9','8','.','.','.','.','6','.'},
        {'8','.','.','.','6','.','.','.','3'},
        {'4','.','.','8','.','3','.','.','1'},
        {'7','.','.','.','2','.','.','.','6'},
        {'.','6','.','.','.','.','2','8','.'},
        {'.','.','.','4','1','9','.','.','5'},
        {'.','.','.','.','8','.','.','7','9'}
    };
    Solution sol;

    sol.solveSudoku(board);
    sol.printBoard(board);

    return 0;
}